﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Spk.Controls.Common;
using System.Threading;

// TODO: Simplify PositionCache - remove ThreadShared, change to private fields

namespace Spk.Controls.Trees
{
    internal class PositionCache
    {
        // Private constants -------------------------------------------------

        /// <summary>
        /// Distance between two entries in position cache. Too low or too high values
        /// will disable the search optimization effect.
        /// </summary>
        private uint step = 2000;

        // Private structures ------------------------------------------------

        private struct PositionCacheEntry
        {
            public VirtualNode Node;
            public int YOffset;

            public PositionCacheEntry(VirtualNode newNode, int newYOffset)
            {
                Node = newNode;
                YOffset = newYOffset;
            }
        }

        private class ThreadShared
        {
            public bool Canceled;
            public VirtualNode Root;

            public ThreadShared(VirtualNode newRoot)
            {
                Canceled = false;
                Root = newRoot;
            }
        }

        // Private fields ----------------------------------------------------

        private Thread thread;
        private ThreadShared shared;

        private VirtualNode root;
        private List<PositionCacheEntry> entries;

        private object threadLock;

        // Private threaded methods ------------------------------------------

        private void ThreadCore(object param)
        {
            param.CheckNull("param");
            if (!(param is ThreadShared))
                throw new ArgumentException("param");

            var shared = param as ThreadShared;

            // Initial processing

            var result = new List<PositionCacheEntry>();

            if (shared.Root == null)
            {
                lock (threadLock)
                {
                    entries = result;
                    root = null;
                }
                return;
            }

            var node = TreeStructure.GetFirstVisible(shared.Root);

            if (node == null)
            {
                lock (threadLock)
                {
                    entries = result;
                    root = shared.Root;
                }
                return;
            }

            uint totalHeight = 0;
            int processed = 0;
            while (node != null && !shared.Canceled)
            {
                if (processed % step == 0)
                    result.Add(new PositionCacheEntry(node, (int)totalHeight));

                totalHeight += node.Height;
                processed++;
                node = TreeStructure.GetNextVisible(node);
            }

            if (!shared.Canceled)
            {
                lock (threadLock)
                {
                    entries = result;
                    root = shared.Root;

                    shared = null;
                }
            }
        }

        // Public methods ----------------------------------------------------

        public PositionCache()
        {
            thread = null;
            shared = null;
            entries = null;
            root = null;
            threadLock = new object();
        }

        /// <summary>
        /// Stops the processing thread (if it is actually working) and
        /// clears the position cache.
        /// </summary>
        public void Invalidate()
        {
            // Canceling thread if it is running
            lock (threadLock)
            {
                if (shared != null)
                {
                    shared.Canceled = true;
                }
            }

            // Has to be done outside critical section, because
            // thread may be just finishing its work and it will
            // try to save the new entries by Thread_Finished event.
            // Doing it inside a critical section would finish
            // in a deadlock.
            if (thread != null && thread.IsAlive)
                thread.Join();

            // Thread is not running anymore, critical section is not needed.
            shared = null;
            entries = null;
            thread = null;
            root = null;
        }

        /// <summary>
        /// Requests the position cache to be constructed in a separate
        /// thread.
        /// </summary>
        public void CreateCache(VirtualNode treeRoot)
        {
            if (thread != null && thread.IsAlive)
                Invalidate();

            // Thread is not running, critical section is not needed.
            shared = new ThreadShared(treeRoot);
            thread = new Thread(ThreadCore);
            thread.Start(shared);
        }

        /// <summary>
        /// Attempts to find cached node, which is the lowest one
        /// placed above or equal to given requiredYOffset.
        /// </summary>
        public bool TryFindNearestEntry(int requiredYOffset, out VirtualNode result, out int position)
        {
            // This has to be done inside a critical section
            // to prevent race condition with the thread 
            // (possibly just finishing its work)
            lock (threadLock)
            {
                if (entries == null || entries.Count == 0)
                {
                    result = null;
                    position = 0;
                    return false;
                }

                int l = 0;
                int h = entries.Count - 1;

                while (l <= h)
                {
                    int i = ((l + h) >> 1);

                    if (entries[i].YOffset <= requiredYOffset)
                        l = i + 1;
                    else
                        h = i - 1;
                }

                if (l == 0)
                {
                    result = null;
                    position = 0;
                }
                else
                {
                    result = entries[l - 1].Node;
                    position = entries[l - 1].YOffset;
                }

                return true;
            }
        }

        /// <summary>
        /// Evaluates absolute y-position of a node using the position cache
        /// </summary>
        public bool TryGetNodeOffset(VirtualNode node, out int position)
        {
            lock (threadLock)
            {
                if (entries == null || entries.Count == 0)
                {
                    position = -1;
                    return false;
                }

                int i = 0;
                while ((i + 1) < entries.Count && TreeStructure.Compare(entries[i + 1].Node, node) != NodeVisualRelationship.Later)
                    i++;

                VirtualNode run = entries[i].Node;
                int currentPosition = entries[i].YOffset;

                while (run != null && run != node)
                {
                    currentPosition += (int)run.Height;
                    run = TreeStructure.GetNextVisible(run);
                }

                if (run != node)
                {
                    position = -1;
                    return false;
                }
                else
                {
                    position = currentPosition;
                    return true;
                }
            }
        }
    }
}
